P7078 [CSP-S2020] 贪吃蛇

发表于 更新于 分类于 ， ， 阅读次数： 作者 Yurchiu ， zzy

这里，先放一个我做的 PPT：link。如果有补充，放在下面。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10;
	struct Snakes//使用运算符重载，可以方便地进行“蛇”运算。 
	{			 //有题解使用 pair。这种东西是将两个数据合并到一块，两者数据类型不必相同。
		ll id,hp;//蛇的体力，编号。 
		bool operator>(Snakes b)//定义蛇的大小。 
		{
			if(this->hp==b.hp) return this->id>b.id;
			return this->hp>b.hp;//this 是一个结构体指针，指向左值的地址。访问结构体成员的值使用 -> 运算符。 
		}
		bool operator<(Snakes b)
		{
			if(this->hp==b.hp) return this->id<b.id;
			return this->hp<b.hp;
		}
		Snakes operator-(Snakes b)//定义蛇的“吃”运算。 
		{
			Snakes _t=*this;//!!! 40->100 qwq
			_t.hp=this->hp-b.hp;
			return _t;
		}
	}s[N];
	ll n,ans=0;
	deque<Snakes>q1,q2;//q1 是初始队列，q2 是吃了之后的队列（单调不升） 
	/*  deque 的用法
	q.front() 返回队首元素。
	q.back() 返回队尾元素。
	q.pop_front() 返回队首元素。
	q.pop_back() 返回队尾元素。
	q.push_front(x) 从队首压入元素 x。
	q.push_back(x) 从队尾压入元素 x。 
	q.size() 返回队列大小。
	q.clear() 清空队列。 
	*/
	void init()
	{
		q1.clear();q2.clear();
		for(ll i=1;i<=n;i++)
			q1.push_front(s[i]);
	}
	Snakes getF()//取最大。 
	{
		Snakes S;
		if(q2.empty() ||//最开始，q2 为空，此时 q1 一定不为空。所以只能选择 q1. 
		   (!q1.empty()&&//首先保证 q1 不为空。 
		   q1.front()>q2.front()))//再保证 q1 比 q2 大。 
		     S=q1.front(),q1.pop_front();
		else S=q2.front(),q2.pop_front();//否则是 q2。 
		return S;
	}
	Snakes getB()//取 q1 最小。 
	{
		Snakes S=q1.back();
		q1.pop_back();
		return S;
	}
	Snakes Check()//检查是否为最弱蛇。 
	{
		Snakes S;
		if(!q1.empty()) S=q1.back();
		if(!q2.empty()&&S>q2.back()) S=q2.back();
		return S; 
	}
	void solve()
	{
		/*  思路： 
		将整场决斗分为两个阶段。
		 
		有一个显然的结论：当前最强的蛇如果吃了最弱的蛇之后，没有变成最弱的蛇，它一定会选择吃。
		引理 1：如果蛇们按照规则一直吃，则吃完后的蛇是越来越弱的。
			    即，若 a_i 比 a_j 先吃，则 a_i > a_j。
		证明 引理 1：最强蛇一定不如以前强，最弱蛇一定不如以前弱。 
		证明 显然的结论：它如果吃了，仍最强，不吃白不吃；
						 它如果吃了，不是最强的，则根据引理 1，之后的蛇吃后，一定比它要弱，一定会想尽办法不死。
						 因此不管如何，它一定死不了。
		把 当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇 这个阶段，定为第一阶段。 
		
		然而，可能当前最强的蛇吃了最弱的蛇之后，变成了最弱的蛇！这时候，它吃不吃，取决于后面的蛇是否吃。
		推理一下： 
		- 如果 a_i 吃了，变成最弱蛇，而 a_j 再吃 a_i 后不是最弱蛇，则 a_j 一定吃，那 a_i 就死了，所以 a_i 不能吃。
		- 如果 a_i 吃了，变成最弱蛇，而 a_j 再吃 a_i 后是最弱蛇，而 a_k 吃了 a_j 不是最弱蛇，则 a_k 一定吃，
		  那 a_j 就死了，所以 a_j 不能吃。所以 a_i 能吃。
		- 吃吃吃，如果最后场上只有两条蛇，则 a_i 无论如何都要吃。
		把 当前最强的蛇吃了最弱的蛇之后都变成最弱的蛇 这个阶段，定为第二阶段。 
		所以这个问题就变成了一个递归的问题，边界是一条蛇打破了第二阶段或场上只有两条蛇了。
		实际上，在程序设计时，不用写递归，因为注意到 a_i 能不能吃和递归层数的奇偶性有关。所以只需一个 while 即可解决。 
		*/
		
		/*  程序设计：
		定义双端队列 q1，q2。我们根据引理 1 找到了单调性，所以不用带 log 的数据结构维护。 
		第一阶段： 
			设 G 要吃 L，变成 T。之后把 T 压入 q2 尾部。 
		    q2 队列中的蛇在第一阶段一定不会被吃（如果被吃，则说明上一个 G 变成了最弱蛇，进入第二阶段）。
		第二阶段：
			只需维护一个最弱蛇，不用再压入队列，因为第二阶段结束后整个决斗就停止了。并统计吃的次数。 
			这个阶段用来看能不能再吃一次。 
		*/
		while(true)
		{
			ll cnt=0;//吃的次数 
			if(q1.size()+q2.size()<=2) {ans=1;return;}
			Snakes L=getB(),G=getF();
			Snakes T=(G-L);
			if(T<q1.back() || q1.empty())//T == L
			{
				ans=q1.size()+q2.size()+2;//答案不必动态统计。 
				while(true)
				{
					cnt++;
					if(q1.size()+q2.size()+1<=2){ans-=(cnt%2==0);/*奇偶性*/return;}
					G=getF();T=(G-T);
					if(T>Check()){ans-=(cnt%2==0);return;}
				}
			}else q2.push_back(T);
		}
	}
	void yzmain()
	{
		ll T,t1,t2,k;
		scanf("%lld",&T);
		for(ll qwq=1;qwq<=T;qwq++)
		{
			if(qwq==1)
			{
				scanf("%lld",&n);
				for(ll i=1;i<=n;i++)
				{
					scanf("%lld",&s[i].hp);
					s[i].id=i;
				}
			}
			else
			{
				scanf("%lld",&k);
				for(ll i=1;i<=k;i++)
				{
					scanf("%lld%lld",&t1,&t2);
					s[t1].hp=t2;
				}
			}
			init();
			solve();
			printf("%lld\n",ans);
		}
		return;
	}
}
int main()
{
	//freopen("snakes.in","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

无注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10;
	struct Snakes
	{
		ll id,hp;
		bool operator>(Snakes b)
		{
			if(this->hp==b.hp) return this->id>b.id;
			return this->hp>b.hp;
		}
		bool operator<(Snakes b)
		{
			if(this->hp==b.hp) return this->id<b.id;
			return this->hp<b.hp;
		}
		Snakes operator-(Snakes b)
		{
			Snakes _t=*this;
			_t.hp=this->hp-b.hp;
			return _t;
		}
	}s[N];
	ll n,ans=0;
	deque<Snakes>q1,q2;
	void init()
	{
		q1.clear();q2.clear();
		for(ll i=1;i<=n;i++)
			q1.push_front(s[i]);
	}
	Snakes getF() 
	{
		Snakes S;
		if(q2.empty() || (!q1.empty()&&q1.front()>q2.front()))
		     S=q1.front(),q1.pop_front();
		else S=q2.front(),q2.pop_front(); 
		return S;
	}
	Snakes getB()
	{
		Snakes S=q1.back();
		q1.pop_back();
		return S;
	}
	Snakes Check()
	{
		Snakes S;
		if(!q1.empty()) S=q1.back();
		if(!q2.empty()&&S>q2.back()) S=q2.back();
		return S; 
	}
	void solve()
	{
		while(true)
		{
			ll cnt=0;
			if(q1.size()+q2.size()<=2) {ans=1;return;}
			Snakes L=getB(),G=getF();
			Snakes T=(G-L);
			if(T<q1.back() || q1.empty())
			{
				ans=q1.size()+q2.size()+2; 
				while(true)
				{
					cnt++;
					if(q1.size()+q2.size()+1<=2){ans-=(cnt%2==0);return;}
					G=getF();T=(G-T);
					if(T>Check()){ans-=(cnt%2==0);return;}
				}
			}else q2.push_back(T);
		}
	}
	void yzmain()
	{
		ll T,t1,t2,k;
		scanf("%lld",&T);
		for(ll qwq=1;qwq<=T;qwq++)
		{
			if(qwq==1)
			{
				scanf("%lld",&n);
				for(ll i=1;i<=n;i++)
				{
					scanf("%lld",&s[i].hp);
					s[i].id=i;
				}
			}
			else
			{
				scanf("%lld",&k);
				for(ll i=1;i<=k;i++)
				{
					scanf("%lld%lld",&t1,&t2);
					s[t1].hp=t2;
				}
			}
			init();
			solve();
			printf("%lld\n",ans);
		}
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}